package leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class LeetCode_day15 {
	
	/**
	 * ! Given a linked list and a value x, 
	 * partition it such that all nodes less than x come 
	 * before nodes greater than or equal to x.
	 * You should preserve the original relative order 
	 * of the nodes in each of the two partitions.
	 * 
	 * For example,
	 * Given 1->4->3->2->5->2 and x = 3,
	 * return 1->2->2->4->3->5.
	 * @param head
	 * @param val
	 */
	public static void partitionList(ListNode head, double val){
		if(head == null) return;
		ListNode divide = new ListNode(null), ind = head, pre = divide, fakeHead = divide;
		fakeHead.next = head;
		
		//without this step, it will fail on this test example, because ListNode(1).next will be itself.
		if(divide.next != null && divide.next.val.doubleValue() < val){
			divide = divide.next;
			ind = divide.next.next;
		}
		while(ind != null){
			if(ind.val.doubleValue() < val){
				ListNode temp = divide.next;
				ListNode temp2 = ind.next;
				divide.next = ind;
				ind.next = temp;
				pre.next = temp2;
				ind = temp2;
				divide = divide.next;
			}else {
				pre = ind;
				ind = ind.next;
			}
		}
		
		head = fakeHead.next;
		System.out.println();
		while(head != null){
			System.out.print(head.val+", ");
			head = head.next;
		}
		System.out.println();
	}
	
	/**
	 * ! Given a string s1, we may represent it as a binary tree by 
	 * partitioning it to two non-empty substrings recursively.
	 * To scramble the string, we may choose 
	 * any non-leaf node and swap its two children.
	 * Given two strings s1 and s2 of the same length, 
	 * determine if s2 is a scrambled string of s1.
	 * 
	 * Analysis:
	 * Another dynamic programming
	 * 首先想到的是递归，简单明了，对两个string进行partition，然后比较四个字符串段。
	 * 但是递归的话，这个时间复杂度比较高。然后想到能否DP，但是即使用DP的话，也要O(n^3)。
	 * 
	 * @param s1
	 * @param s2
	 */
	public static void scrambleString(String s1, String s2){
		
	}
	/**
	 * Given two sorted integer arrays A and B, merge B into A as one sorted array.
	 * Note:
	 * You may assume that A has enough space to hold additional elements from B. 
	 * The number of elements initialized in A and B are m and n respectively.
	 * @param a
	 * @param b
	 */
	public static void mergeSortedArray(int[] a, int[] b, int m, int n){
		if(a == null || b == null || a.length < m+n) return;
		for(int i = n ; i < n+m ; i++) a[i] = a[i-n];//move all elements of a backward.
		int inda = n, indb = 0, ind = 0;
		for(; ind < m+n && inda < m+n && indb < n; ind++){
			if(a[inda] > b[indb]) {
				a[ind] = b[indb];
				indb++;
			}
			else {
				a[ind] = a[inda];
				inda++;
			}
		}
		
		System.out.println();
		for(int i = 0 ; i < m+n ; i++) 
			System.out.print(a[i]);
		System.out.println();
		
	}
	
	/**
	 * ！ The gray code is a binary numeral system where two successive values differ in only one bit.
	 * Given a non-negative integer n representing the total number of 
	 * bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
	 * For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
	 * 00 - 0
	 * 01 - 1
	 * 11 - 3
	 * 10 - 2
	 * Note:
	 * For a given n, a gray code sequence is not uniquely defined.
	 * For example, [0,2,3,1] is also a valid gray code 
	 * sequence according to the above definition.
	 * 
	 * Analysis:
	 * let each gray code to be a vertex of the super cube. 
	 * An edge between them means they are successive.
	 * Then the question turns out to be find all vertices and 
	 * a path to connect all vertices in hyper cube.
	 * 
	 * Snake-in-the-box problem:
	 * find a certain kind of path along the edges of a hyper cube.
	 * 
	 * By wiki: Constructing an n-bit gray code
	 * can be generated recursively from the list for n-1 bits
	 * by reflecting the list.
	 * (listing the entries in reverse order)
	 * ex:
	 * 2-bit: 00,01,11,10
	 * Reflected:      10,11,01,00
	 * 3-bit: 000,001,011,010
	 * 	               110,111,101,100
	 * @param n
	 */
	public static void grayCode(int n, List<List<Boolean>> ress){
		if(n < 1) return;
		if(n == 1){
			List<Boolean> list1 = new ArrayList<Boolean>();
			List<Boolean> list2 = new ArrayList<Boolean>();
			list1.add(false);
			list2.add(true);
			ress.add(list1); ress.add(list2);
		}else{
			grayCode(n-1, ress);
			List<List<Boolean>> ressCopy = new ArrayList<List<Boolean>>();
			ressCopy.addAll(ress);
			ress.clear();
			for(List<Boolean> l : ressCopy){
				List<Boolean> ll = new ArrayList<Boolean>();
				ll.addAll(l);
				ll.add(false);
				ress.add(ll);
			}
			for(List<Boolean> l : ressCopy){
				List<Boolean> ll = new ArrayList<Boolean>();
				ll.addAll(l);
				ll.add(true);
				ress.add(ll);
			}
		}
	}
	
	/**
	 * A message containing letters from A-Z is 
	 * being encoded to numbers using the following mapping:
	 * 'A' -> 1
	 * 'B' -> 2
	 * ...
	 * 'Z' -> 26
	 * Given an encoded message containing digits, 
	 * determine the total number of ways to decode it.
	 * For example,
	 * Given encoded message "12", it could be decoded 
	 * as "AB" (1 2) or "L" (12).
	 * The number of ways decoding "12" is 2.
	 * @param mesg
	 */
	public static void decodeWays(String mesg, int ind, List<Character>decode, List<List<Character>> decodings){
		if(mesg == null) return;
		if(ind >= mesg.length()) {
			decodings.add(decode);
			return;
		}
		int cur = Character.getNumericValue(mesg.charAt(ind));
		if(ind + 1 < mesg.length()){
			int anotherCur = Character.getNumericValue(mesg.charAt(ind)) * 10 + Character.getNumericValue(mesg.charAt(ind+1));;
			if(anotherCur <= 26){
				List<Character> newDec = new ArrayList<Character>();
				newDec.addAll(decode);
				newDec.add((char) ('A'-1+anotherCur));
				decodeWays(mesg, ind+2, newDec, decodings);
			}
		}
		decode.add((char)('A'-1+cur));
		decodeWays(mesg, ind+1, decode, decodings);
	}
	
	/**
	 * ! Given a collection of integers that might contain duplicates, S, 
	 * return all possible subsets.
	 * Note:
	 * Elements in a subset must be in non-descending order.
	 * The solution set must not contain duplicate subsets.
	 * For example,
	 * If S = [1,2,2], a solution is:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

	 * Analysis:
	 * Say n is the # of the elements,
when n=1, subsets :  {}, {"1"},  "i" means the ith element.
when n=2, subsets:   {}, {"1"}, {"2"}, {"1", "2"}
when n=3, subsets:   {}, {"1"}, {"2"}, {"1", "2"}, {"3"}, {"1","3"}, {"2","3"}, {"1", "2","3"}
So, the way of generating subsets is:
From 2 to n, COPY the previous subsets, add the current element, push back to the subsets list.

Then we take the duplicates into account, the same example:
when n=1, subsets :  {}, {"1"},  "i" means the ith element.
when n=2, subsets:   {}, {"1"}, {"2"}, {"1", "2"}
when n=3, but "2"=="3" subsets: 
   {}, {"1"}, {"2"}, {"1", "2"}, {"3"}, {"1","3"}, {"2","3"}, {"1", "2","3"}
since "2"=="3", which truly is:
   {}, {"1"}, {"2"}, {"1", "2"}, {"2"}, {"1","2"}, {"2","2"}, {"1", "2","2"}
where the bold ones are not needed.
So, how these two subsets are generated? They are from the subsets of n=1.

In sum up, when meet the same element as previous one, 
then generate new subsets ONLY from the subsets generated from previous iteration, 
other than the whole subsets list.
	 * @param s
	 */
	public static void subsetsII(int[] s){
		if(s == null) return;
		List<Integer> path = new ArrayList<Integer>();
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		Arrays.sort(s);
		sub(s, 0, path, result);
		
		for(List<Integer> l : result){
			for(int i : l)
				System.out.print(i+",");
			System.out.println();
		}
			
	}
	
	private static void sub(int[] s, int begin, List<Integer> path, List<List<Integer>> result){
		result.add(path);
		for(int i = begin ; i < s.length ; i++){
			if(i != begin && s[i] == s[i-1]) continue;
			List<Integer> newpath = new ArrayList<Integer>();
			newpath.addAll(path);
			newpath.add(s[i]);
			sub(s, i+1, newpath, result);
		}
	}
	
	/**
	 * ! Reverse a linked list from position m to n. Do it in-place and in one-pass.
	 * For example:
	 * Given 1->2->3->4->5->NULL, m = 2 and n = 4,
	 * return 1->4->3->2->5->NULL.
	 * @param head
	 * @param m
	 * @param n
	 */
	public static void reverseLinkedListII(ListNode head, int m, int n){
		if(head == null) return;
		if(m < 0 || n < 0 || n < m) return;
		ListNode pre = new ListNode(null), after = null, newHead = pre;
		pre.next = head;
		ListNode ind = head;
		
		while(m >= 0){
			pre = ind;
			ind = ind.next;
			m--;
		}
		int t = n - m;
		ListNode start = pre, tail = ind;
		after = ind.next;
		while(t > 0){
			ind.next = pre;
			pre = ind;
			ind = after;
			after = ind.next;
			t--;
		}
		start.next.next = after;
		start.next = ind;
		System.out.println();
		while(newHead != null){
			if(newHead.val != null)
				System.out.print(newHead.val+", ");
			newHead = newHead.next;
		}
		System.out.println();
		
	}
	
	/**
	 * Given a string containing only digits, 
	 * restore it by returning all possible valid IP address combinations.
	 * For example:
	 * Given "25525511135",
	 * return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
	 * @param s
	 */
	public static void restoreIPAddress(String s){
		
	}
	
	/**
	 * Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
	 * For example,
	 * Given:
	 * s1 = "aabcc",
	 * s2 = "dbbca",
	 * When s3 = "aadbbcbcac", return true.
	 * When s3 = "aadbbbaccc", return false.
	 * @param s1
	 * @param s2
	 * @param s3
	 */
	public static boolean interleavingString(String s1, String s2, String s3, int ind1, int ind2, int ind3){
		if(s1 == null || s2 == null || s3 == null) return false;
		if(ind1 < 0 || ind2 < 0 || ind3 < 0 || ind1 > s1.length() || ind2 > s2.length() || ind3 > s3.length()) return false;
		if(s1.length() + s2.length() != s3.length()) return false;
		if(ind1 == s1.length() && ind2 == s2.length() && ind3 == s3.length()) return true;
	
		
		if(ind1 < s1.length() && s1.charAt(ind1) == s3.charAt(ind3)) 
			if(interleavingString(s1,s2,s3,ind1+1, ind2, ind3+1)) return true;

		if(ind2 < s2.length() && s2.charAt(ind2) == s3.charAt(ind3)) 
			if(interleavingString(s1,s2,s3,ind1, ind2+1, ind3+1)) return true;
		
		return false;
	}
	
	/**
	 * Given a string S and a string T, count the number of distinct subsequences of T in S.
	 * A subsequence of a string is a new string which is formed from the original 
	 * string by deleting some (can be none) of the characters without disturbing 
	 * the relative positions of the remaining characters. 
	 * (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
	 * Here is an example:
	 * S = "rabbbit", T = "rabbit"
	 * Return 3.
	 * @param s
	 * @param t
	 */
	public static void distinctSubsequence(String s, String t, int inds, int indt, int[] num){
		if(s == null || t == null) return;
		if(indt == t.length()){
			num[0]+=1;
			return;
		}
		if(inds >= s.length()) return;
		if(s.charAt(inds) == t.charAt(indt)) distinctSubsequence(s,t,inds+1,indt+1,num);
		distinctSubsequence(s,t,inds+1,indt,num);
	}
	
	/**
	 * Given numRows, generate the first numRows of Pascal's triangle.
	 * For example, given numRows = 5,
	 * Return
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
	 * @param rowNum
	 */
	public static void pascasTriangle(int rowNum){
		if(rowNum < 1) return;
		int[][] triangle = new int[rowNum][];
		triangle[0] = new int[]{1};
		for(int i = 1 ; i < rowNum ; i++){
			int[] nextRow = new int[i+1];
			nextRow[0] = 1; nextRow[i] = 1;
			for(int j = 1 ; j < i ; j++){
				nextRow[j] = triangle[i-1][j-1]+triangle[i-1][j];
			}
			triangle[i] = nextRow;
		}
		System.out.println();
		for(int i = 0 ; i < rowNum ; i++){
			for(int j : triangle[i])
				System.out.print(j+", ");
			System.out.println();
		}
		System.out.println();
	}
	
	/**
	 * Given an index k, return the kth row of the Pascal's triangle.
	 * For example, given k = 3,
	 * Return [1,3,3,1].
	 * Note:
	 * Could you optimize your algorithm to use only O(k) extra space?
	 * @param k
	 */
	public static void pascasTriangleII(int k){
		if(k < 1) return;
		int[] res = new int[k];
		int[] pre = new int[k];
		pre[0] = 1; pre[1] = 1;
		res[0] = 1; 
		for(int i = 1 ; i < k ; i++){
			res[i] = 1;
			for(int j = 1 ; j < i ; j++){
				res[j] = pre[j-1] + pre[j];
			}
			pre = Arrays.copyOf(res, i+1);//notice
		}
		
		System.out.println();
		for(int i = 0 ; i < k ; i++) System.out.print(res[i]+", ");
		System.out.println();
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ListNode head = new ListNode(1);
		head.next = new ListNode(4);
		head.next.next = new ListNode(3);
		head.next.next.next = new ListNode(2);
		head.next.next.next.next = new ListNode(5);
		head.next.next.next.next.next = new ListNode(2);
		//reverseLinkedListII(head, 2, 4);
		
		partitionList(head, 3.0);

		List<List<Boolean>> ress = new ArrayList<List<Boolean>>();
		grayCode(3,ress);
		System.out.println();
		for(List<Boolean> l : ress){
			for(Boolean b : l)
				System.out.print((b?1:0));
			System.out.println();
		}
		System.out.println();
		
		List<List<Character>> ress1 = new ArrayList<List<Character>>();
		decodeWays("12", 0, new ArrayList<Character>(), ress1);
		for(List<Character> l : ress1){
			for(Character c : l)
				System.out.print(c);
			System.out.println();
		}
		
		System.out.println(interleavingString("aabcc","dbbca","aadbbcbccc",0,0,0));
		int[] num = new int[]{0};
		distinctSubsequence("rabbbit","rabbit", 0,0,num);
		System.out.println(num[0]);
		pascasTriangle(5);
		pascasTriangleII(5);
		subsetsII(new int[]{1,2,2});
 	}

}
